#include <iostream>
#include <algorithm>
#include <vector>
#include <ctime>
#include <cmath>

int const maxn = 10007;
bool vis[maxn];
int q[maxn];
int n, m, color[2], len;

void dfs(int x, int co, std::vector<std::vector<int> > const & g)
{
	vis[x] = true;
	color[co]++;
	int len = g[x].size();
	for (int i = 0; i < len; i++) {
		int v = g[x][i];
		if (!vis[v]) {
			dfs(v, 1-co, g);
		}
	}
}

int main()
{
	std::ios::sync_with_stdio(false);
	int T;
	std::cin >> T;
	int ran = 8000000/T;
	std::srand(time(0));
	for (int ti = 0; ti < T; ti++) {
		std::vector<std::vector<int> > g;
		std::cin >> n >> m;
		g.resize(n);
		std::fill(vis, vis + n, 0);
		for (int i = 0, x, y; i < m; i++) {
			std::cin >> x >> y;
			x--; y--;
			g[x].push_back(y); g[y].push_back(x);
		}
		len = 0;
		int sum = 0;
		for (int i = 0; i < n; i++) {
			color[0] = color[1] = 0;
			if (!vis[i]) dfs(i, 0, g);
			q[len++] = color[1] - color[0];
			sum += color[1] - color[0];
		}

//		std::cout << "len: " << len << '\n'; for (int i = 0; i < len; i++) std::cout << q[i] << ' '; std::cout << '\n'; 

		for (int i = 0; i < ran; i++) {
			int t = (rand() % len);
			if (std::abs(sum - q[t] - q[t]) < std::abs(sum)) {
				sum = sum - q[t] - q[t];
				q[t] = -q[t];
			}
		}

		sum = std::abs(sum);
		int a = (n + sum) / 2;
		int b = n - a;
		std::cout << a * b - m << '\n';
	}
}

